public class Solution124 {

    int res = Integer.MIN_VALUE;

    private int maxSubPathSum(TreeNode node) {
        if(node == null){
            return 0;
        }
        int val = node.val, leftMaxVal = maxSubPathSum(node.left), rightMaxVal = maxSubPathSum(node.right);
        res = Math.max(res, leftMaxVal + rightMaxVal + val);
        return Math.max(0, Math.max(leftMaxVal, rightMaxVal) + val);
    }

    public int maxPathSum(TreeNode root) {
        maxSubPathSum(root);
        return res;
    }
}
